package com.zklh.leetcode.top100;

/**
 * 搜索二维矩阵算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/11/2
 */
public class Solution74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix[0][0] > target) {
            return false;
        }

        // 先用二分查找定位数字在哪一行
        int up = 0, down = matrix.length-1;
        while (up < down - 1) {
            int mid = (up + down) / 2;
            if (matrix[mid][0] <= target) {
                up = mid;
            } else if (matrix[mid][0] > target){
                down = mid;
            }
        }

        int row = matrix[down][0] <= target ? down : up;
        int left = 0, right = matrix[0].length-1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (matrix[row][mid] < target) {
                left = mid + 1;
            } else if (matrix[row][mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
                right = mid;
            }
        }
        return matrix[row][left] == target;
    }

    public static void main(String[] args) {
        Solution74 solution74 = new Solution74();
        int[][] matrix = {{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int target = 10;
        System.out.println(solution74.searchMatrix(matrix, target));
    }
}